/*
 * @Author: your name
 * @Date: 2024-03-28 11:14:48
 * @LastEditTime: 2024-03-28 12:00:11
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\707.设计链表.cpp
 */
/*
 * @lc app=leetcode.cn id=707 lang=cpp
 *
 * [707] 设计链表
 */

// @lc code=start
class MyLinkedList {
public: 
    
    // 定义链表节点
    struct ListNode{
        int val;
        ListNode* next;
        ListNode(int val):val(val),next(nullptr){}
    };
    int _size;
    ListNode* dummy;
    MyLinkedList() {
        // 初始化一个链表头结点，该头结点是虚拟节点
        dummy= new ListNode(0);
        _size = 0;
    }
    
    int get(int index) {
        // 超出index范围的部分返回-1
        if(index > (_size-1) || index < 0){
            return -1;
        }
        ListNode* cur = dummy->next;
        while(index--){
            cur = cur->next;
        }
        return cur->val;
    }       
    
    void addAtHead(int val) {
        
        ListNode* tmp = dummy->next;
        ListNode* new_node = new ListNode(val);
        dummy->next = new_node;
        new_node->next = tmp; 
        _size++;
        cout<<"addAtHead success"<<endl;
    }
    
    void addAtTail(int val) {
        ListNode* cur = dummy;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        ListNode* new_node = new ListNode(val);
        cur->next = new_node;
        _size++;
        cout<<"addAtTail success"<<endl;
    }
    
    void addAtIndex(int index, int val) {
        if(index > _size){
            return;
        }
        else if(index == _size){
            addAtTail(val);
        }
        else if(index <= 0){
            addAtHead(val);
        }
        else{
            ListNode* cur = dummy->next;
            while(--index){
                cur = cur->next;
            }
            ListNode* tmp = cur->next;
            ListNode* new_node = new ListNode(val);
            cur->next = new_node;
            new_node->next = tmp;
            _size++;
        }
        cout<<"addAtIndex success"<<endl;
    }
    
    void deleteAtIndex(int index) {
        if(index >=0 && index < _size){
            ListNode* cur = dummy;
            while(index--){
                cur = cur->next;
            }
            ListNode* tmp = cur->next;
            cur->next = tmp->next;
            delete tmp;
            //delete命令指示释放了tmp指针原本所指的那部分内存，
            //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
            //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
            //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
            tmp = nullptr;
            _size--;
            cout<<"deleteAtIndex success"<<endl;
        }
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
// @lc code=end

